package Heap;

/**
 * @version 1.0
 * @Author jsc
 * @Date 2025/4/15 20:35
 * @注释 手写小根堆
 */
public class MinHeap {
    // 存储堆元素的数组
    private int[] heap;
    // 存储堆的最大容量
    private int capacity;
    private int size;

    MinHeap(int capacity) {
        this.capacity = capacity;
        heap = new int[capacity];
        size = 0;
    }

    // 默认容量设置为10，大于则进行扩容
    MinHeap() {
        heap = new int[10];
        size = 0;
        capacity = 10;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    // 获取根元素
    public int peek() {
        if (size == 0) {
            throw new RuntimeException("Heap is empty");
        }
        return heap[0];
    }

    private void swap(int min, int pos) {
        int temp = heap[min];
        heap[min] = heap[pos];
        heap[pos] = temp;
    }

    // 下沉操作
    private void down(int pos) {
        while (true) {
            int min = pos;
            int leftCHild = pos * 2 + 1;
            int rightCHild = pos * 2 + 2;

            if (leftCHild < size && heap[leftCHild] < heap[min]) {
                min = leftCHild;
            }

            if (rightCHild < size && heap[rightCHild] < heap[min]) {
                min = rightCHild;
            }

            if (min == pos) {
                break;
            }
            swap(min, pos);
            pos = min;
        }
    }

    // 上浮操作
    private void up() {
        int pos = size - 1;
        while (pos > 0) {
            int parent = (pos - 1) / 2;

            if (heap[pos] > heap[parent]) {
                break;
            }

            swap(pos, parent);
            pos = parent;
        }
    }

    // 弹出根元素
    public int poll() {
        if (size == 0) {
            throw new RuntimeException("Heap is empty");
        }
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        down(0);
        return min;
    }

    // 插入元素
    public void offer(int value) {
        if (size == capacity) {
            resize();
        }
        heap[size++] = value;

        up();
    }

    private void resize() {
        capacity = capacity * 2;
        int[] newHeap = new int[capacity];
        System.arraycopy(heap, 0, newHeap, 0, size);
        heap = newHeap;
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap();
        minHeap.offer(4);
        minHeap.offer(1);
        minHeap.offer(7);
        minHeap.offer(8);
        minHeap.offer(9);
        minHeap.offer(0);
        minHeap.offer(100);
        minHeap.offer(101);
        minHeap.offer(1077);
        minHeap.offer(81);
        minHeap.offer(92);
        minHeap.offer(56);

       while (!minHeap.isEmpty()) {
           System.out.println(minHeap.poll());
       }
    }
}
